// 双指针
// 解法一：
class Solution {
    public:
        int trap(vector<int>& height) {
            int l = 0, r = height.size() - 1;
            int v = 0, min_h = 0;
            while (l < r)
            {
                int h = min(height[l], height[r]);
                if (h > min_h)
                {
                    v += (r - l) * (h - min_h);
                    min_h = h;
                }
                if (height[l] < height[r]) v -= min(height[l++], min_h);
                else v-= min(height[r--], min_h);
            }
            return v;
        }
    };
    
// 解法二：
class Solution {
    public:
        int trap(vector<int>& height) {
            int l = 0, r = height.size() - 1;
            int v = 0, max_l = 0, max_r = 0;
            while (l < r)
            {
                max_l = max(max_l, height[l]);
                max_r = max(max_r, height[r]);
                if (height[l] < height[r]) v += max_l - height[l++];
                else v += max_r - height[r--];
            }
            return v;
        }
    };
    